package jm.algorithm.graph;

import java.util.*;

/**
 * @Description 图接口
 * @date 2022/5/10 20:31
 */
public abstract class Graph<V,E>{

    protected WeightManager<E> weightManager;

    public Graph() {}

    public Graph(WeightManager<E> weightManager) {
        this.weightManager = weightManager;
    }

    /**
     * 获取边的数量
     * @return 边数量
     */
    public abstract int edgeSize();

    /**
     * 获取顶点数量
     * @return 顶点数量
     */
    public abstract int verticesSize();

    /**
     * 添加一个顶点
     * @param v 顶点
     */
    public abstract void addVertex(V v);

    /**
     * 两个顶点之间添加一个边
     * @param from 起点
     * @param to 终点
     */
    public abstract void addEdge(V from, V to);

    /**
     * 两个顶点之间添加一个携带权值的边
     * @param from 起点
     * @param to 终点
     * @param weight 权值
     */
    public abstract void addEdge(V from, V to, E weight);

    /**
     * 删除一个顶点
     * @param v 顶点
     */
    public abstract void removeVertex(V v);

    /**
     * 删除一条边
     * @param from 起点
     * @param to 终点
     */
    public abstract void removeEdge(V from, V to);

    /**
     * 广度优先搜索
     * @param v
     */
    public abstract void bfs(V v, VertexVisitor<V> visitor);

    /**
     * 深度优先搜索
     * @param v
     */
    public abstract void dfs(V v, VertexVisitor<V> visitor);

    /**
     * 使用栈实现深度优先搜索
     * @param v
     */
    public abstract void difOfStack(V v, VertexVisitor<V> visitor);

    /**
     * dfs 和 bfs 遍历是外部获取值
     * @param <V>
     */
    public interface VertexVisitor<V> {
        boolean visit(V v);
    }

    /**
     * 拓扑排序
     * @return
     */
    public abstract List<V> topologicalSort();

    /**
     * 最小生成树
     * @return
     */
    public abstract Set<EdgeInfo<V,E>> mst();

    /**
     * 最短路径
     * @return
     */
    public abstract Map<V,E> shortestPath(V begin);

    /**
     * 包含路径信息的最短路径
     * @param begin
     * @return
     */
    public abstract Map<V,PathInfo<V, E>> shortestPathHaveInfo(V begin);

    /**
     * 多源最短路径
     * @return
     */
    public abstract Map<V, Map<V, PathInfo<V, E>>> shortestPath();

    /**
     * 权值内部接口设计
     * @param <E>
     */
    public interface WeightManager<E> {
        /**
         * 比较值的大小
         * @param w1
         * @param w2
         * @return
         */
        int compare(E w1, E w2);

        /**
         * 两个值相加的结果
         * @param w1
         * @param w2
         * @return
         */
        E add(E w1, E w2);
        E zero();
    }

    /**
     * 路径信息封装
     * @param <V>
     * @param <E>
     */
    public static class PathInfo<V, E>{
        // 总权值信息
        private E weight;
        // 路径信息
        List<EdgeInfo<V,E>> edges = new LinkedList<>();

        public PathInfo() {
        }

        public PathInfo(E weight) {
        }

        public E getWeight() {
            return weight;
        }

        public void setWeight(E weight) {
            this.weight = weight;
        }

        public List<EdgeInfo<V, E>> getEdges() {
            return edges;
        }

        public void setEdges(List<EdgeInfo<V, E>> edges) {
            this.edges = edges;
        }

        @Override
        public String toString() {
            return "PathInfo{" +
                    "weight=" + weight +
                    ", edges=" + edges +
                    '}';
        }
    }

    /**
     * 返回边的节点设计
     * @param <V>
     * @param <E>
     */
    public static class EdgeInfo<V,E>{
        // 起点值
        private V from;
        // 终点值
        private V to;
        // 权值
        private E weight;
        public EdgeInfo(V from, V to, E weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        public V getFrom() {
            return from;
        }

        public void setFrom(V from) {
            this.from = from;
        }

        public V getTo() {
            return to;
        }

        public void setTo(V to) {
            this.to = to;
        }

        public E getWeight() {
            return weight;
        }

        public void setWeight(E weight) {
            this.weight = weight;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            EdgeInfo<?, ?> edgeInfo = (EdgeInfo<?, ?>) o;
            return Objects.equals(from, edgeInfo.from) && Objects.equals(to, edgeInfo.to) && Objects.equals(weight, edgeInfo.weight);
        }

        @Override
        public int hashCode() {
            return Objects.hash(from, to, weight);
        }

        @Override
        public String toString() {
            return "EdgeInfo{" +
                    "from=" + from +
                    ", to=" + to +
                    ", weight=" + weight +
                    '}';
        }
    }
}
